#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath> // For std::abs

using namespace std;

class Solution 
{
public:
    std::vector<int> sortedSquares(std::vector<int>& nums) {
        int n = nums.size();
        std::vector<int> result(n); // 提前分配好结果数组的空间

        int left = 0;
        int right = n - 1;
        int write_ptr = n - 1;

        while (left <= right) {
            // 比较两端元素的绝对值
            if (std::abs(nums[left]) > std::abs(nums[right])) {
                result[write_ptr] = nums[left] * nums[left];
                left++;
            } else {
                result[write_ptr] = nums[right] * nums[right];
                right--;
            }
            // 结果数组的指针向前移动
            write_ptr--;
        }
        return result;
    }
};
    
int main()
{
    Solution s;
    
    // 测试案例1：包含正数和负数的数组
    vector<int> nums1 = {-4, -1, 0, 3, 10};
    cout << "原始数组: ";
    for(int num : nums1) {
        cout << num << " ";
    }
    cout << endl;
    
    vector<int> result1 = s.sortedSquares(nums1);
    cout << "平方后排序: ";
    for(int num : result1) {
        cout << num << " ";
    }
    cout << endl; // 输出: 0 1 9 16 100
    
    // 测试案例2：全为负数的数组
    vector<int> nums2 = {-7, -3, -2, -1};
    cout << "\n原始数组: ";
    for(int num : nums2) {
        cout << num << " ";
    }
    cout << endl;
    
    vector<int> result2 = s.sortedSquares(nums2);
    cout << "平方后排序: ";
    for(int num : result2) {
        cout << num << " ";
    }
    cout << endl; // 输出: 1 4 9 49
    
    return 0;
}
